
13
國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
The partition problem (分割問題):
給予一組正整數的集合S={a
1
, a
2
, … , a
n
},問: 是否可以將其分割成兩
個子集合S
1
與S
2
,而此兩個子集合的個別總和相等。
Ex: Let S = {13, 2, 17, 20, 8}. The answer to this problem instance is "
yes
yes"
because we can partition S into S
1
= {13, 17} and S
2
= {2, 20, 8}.
The Sum of Subset Problem (部份集合的和問題):
給予一組正整數的集合S={a
1
, a
2
, … , a
n
}及一個常數c,問: 集合S中是
否存在一組子集合S’
,此子集合S’的數字總合為c。
Ex: Let
S
= {12, 9, 33, 42, 7, 10, 5} and
c
= 24.
{ The answer of this problem instance is "
yes
yes" as there exists
S’
= {9, 10, 5}
and the sum of the elements in
S’
is equal to 24.
{ If
c
is 6, the answer will be "
no
no".